package likou;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/02 15:56
 */
public class _76 {
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }

    public String minWindow2(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int[] map = new int[256];
        for (char c : tt) {
            map[c]++;
        }
        int left = 0;
        int right = 0;
        int match = tt.length;
        int minlen = Integer.MAX_VALUE;
        int start = -1;
        while (right < ss.length) {
            map[ss[right]]--;
            if (map[ss[right]] >= 0) {
                match--;
            }
            if (match == 0) {
                while (map[ss[left]] < 0) {
                    map[ss[left++]]++;
                }
                if (minlen > right - left + 1) {
                    minlen = right - left + 1;
                    start = left;
                }
                map[ss[left++]]++;
                match++;
            }
            right++;
        }
        return start == -1 ? "" : s.substring(start, start + minlen);
    }

    public static String minWindow(String source, String target) {
        // write your code here
        int end = 0;
        int slen = source.length();
        int tlen = target.length();
        char[] scs = source.toCharArray();
        char[] tcs = target.toCharArray();
        if (slen < tlen) {
            return "";
        }
        int[] tnums = new int[100];
        for (int i = 0; i < tlen; i++) {
            tnums[tcs[i] - 'A']++;
        }
        int[] nums = new int[tnums.length];
        for (int i = slen - 1; i >= 0; i--) {
            if (tnums[scs[i] - 'A'] > nums[scs[i] - 'A']) {
                nums[scs[i] - 'A']++;
                tlen--;
            }
            if (tlen == 0) {
                end = i;
                break;
            }
        }
        String res = source + "1";
        tlen = target.length();
        for (int i = 0; i <= end; i++) {
            if (tnums[scs[i] - 'A'] > 0) {
                String str = getStr(i, scs, tnums, tlen);
                res = res.length() > str.length() ? str : res;
            }
        }
        return res.equals(source + "1") ? "" : res;
    }

    public static String getStr(int start, char[] scs, int[] tnums, int tlen) {
        int i = start;
        int[] nums = new int[tnums.length];
        for (; i < scs.length && tlen > 0; i++) {
            if (nums[scs[i] - 'A'] < tnums[scs[i] - 'A']) {
                tlen--;
                nums[scs[i] - 'A']++;
            }
        }
        return new String(scs, start, i - start);
    }
}
